package demo;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main1 {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(null, 1);
        System.out.println(map.get(null));
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), c = sc.nextInt();
        int[] p = new int[n + 1];
        int[] v = new int[n + 1];
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            p[i] = sc.nextInt();
            sum += v[i];
        }
        if(sum < c)
        {
            System.out.println("Error!");
            return ;
        }

        int[][] dp = new int[n + 1][c + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= c; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= c; j++) {
                dp[i][j] = dp[i - 1][j];

                if(j - v[i] >= 0 && dp[i - 1][j - v[i]] != Integer.MAX_VALUE)
                {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - v[i]] + p[i]);
                }

                if(j - 2 * v[i] >= 0 && dp[i - 1][j - v[i] * 2] != Integer.MAX_VALUE)
                {
//                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - v[i]] + p[i]);
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 2 * v[i]] + 2 * p[i]);
                }
            }
        }
        System.out.println(dp[n][c]);
    }
}